#include"QuickSort.h"

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void PartSort1(int* a, int left, int right,int *countB,int *countY)
{

	if (left >= right)
	{
		return;
		(*countB)++;

	}

	int keyi = left;

	int begin = keyi;
	int end = right;   
	while (begin < end)
	{
		while (begin<end && a[end]<a[keyi])
		{
			(*countB)++;
			end--;
		}
		
		while (begin < end && a[begin] >= a[keyi])
		{
			(*countB)++;
			begin++;
		}

		if (begin < end)
		{
			(*countY)++;

			swap(&a[begin], &a[end]);
		}
	}
	swap(&a[keyi], &a[begin]);
	PartSort1(a, left, begin-1,countB,countY);
	PartSort1(a, begin+1, right,countB,countY);

}

void PartSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int keyi = left;

	int begin = left;
	int end = right;
	int tmp=a[end];
	while(begin<end)
	{
		
		while (begin<end && a[end]>a[keyi])
		{
			end--;
		}
		tmp = a[end];
		while (begin < end && a[begin] < a[keyi])
		{
			begin++;
		}
		if (begin < end)
		{
			a[end] = a[begin];
			a[begin] = tmp;
		}
	}
	a[end] = a[keyi];
	a[keyi] = tmp;

	PartSort2(a, left, begin - 1);
	PartSort2(a, begin + 1, right);
	
}

/*void PartSort3(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int keyi = left;

	int *begin = &left;
	int* end = left + 1;
	int tmp = *end;

	while()


}*/